#pragma once

//C++ Hand File
#include <iostream>
using std::pair;
using std::make_pair;
using std::cout;
using std::endl;


//C Hand File
#include <cassert>

enum Color //红黑树颜色标记
{
	RED, //红色
	BLACK, //黑色
};

namespace my_rb_tree
{
	template<class K,class V>
	struct RBTreeNode
	{
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		pair<K, V> _data;
		Color _col;

		RBTreeNode(const pair<K, V>& data)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _col(RED) //新节点默认红色
		{}
	};


	template<class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
		RBTree()
			:_root(nullptr)
		{}

		RBTree(const RBTree<K, V>& rbt)
			:_root(nullptr)
		{
			_root = copy(rbt._root);
		}

		bool Insert(const pair<K, V>& data)
		{
			if (!_root) //无节点 直接插入 根节点为黑
			{
				_root = new Node(data);
				_root->_col = BLACK;
				return true;
			}

			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data.first > data.first) //当前节点>插入值
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data.first < data.first) //当前节点<插入值
				{
					parent = cur;
					cur = cur->_right;
				}
				else //相同 返回false
				{
					return false;
				}
			}

			cur = new Node(data);
			if (parent->_data.first > cur->_data.first) //判断新节点应该插在左边还是右边
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

			//开始调整
			while (parent && parent->_col == RED) //两个红色则需要调整
			{
				Node* grandfather = parent->_parent;
				//判断祖父的左右找叔叔
				if (grandfather->_left == parent) //父节点是祖父的左
				{
					Node* uncle = grandfather->_right;//叔叔是祖父的右
					if (uncle && uncle->_col == RED) //叔叔存在且为红
					{
						parent->_col = BLACK; //父亲和叔叔变黑
						uncle->_col = BLACK;
						grandfather->_col = RED; //祖父变红

						cur = grandfather; //更新节点 继续检测
						parent = cur->_parent;
					}
					else //叔叔不存在或叔叔为黑
					{
						if (cur == parent->_left) //cur是parent的左 - 右旋 - 左左
						{
						//     g
						//    p e
						//   c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else //cur是parent的右边 - 双旋 - 左右旋
						{
						//     g          g         
						//   p   e ->   p   e
						//    c       c    
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
							parent->_col = RED;
						}
						break; //调整完可以跳出
					}
				}
				else
				{
					Node* uncle = grandfather->_left;//叔叔是祖父的左
					if (uncle && uncle->_col == RED) //叔叔存在且为红
					{
						parent->_col = BLACK; //父亲和叔叔变黑
						uncle->_col = BLACK;
						grandfather->_col = RED; //祖父变红

						cur = grandfather; //更新节点 继续检测
						parent = cur->_parent;
					}
					else //叔叔不存在或叔叔为黑
					{
						if (cur == parent->_right) //cur是父亲的右边 - 左旋 - 右右
						{ //变色形式与左左一样
						//     g
						//   e   p
						//         c
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else
						{
						//     g
						//   e   p
						//      c
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
							parent->_col = RED;
						}
						break; //调整完可以跳出
					}
				}
			}

			_root->_col = BLACK; //根节点始终为黑
			return true;
		}

		void midorder() //中序遍历
		{
			_midorder(_root);
		}

		bool IsBalanceTree()
		{
			int leftblack = 0;
			int rightblack = 0;

			Node* cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
					++leftblack;

				cur = cur->_left;
			}
			cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
					++rightblack;

				cur = cur->_right;
			}
			if(leftblack == rightblack)
				return _Check(_root, 0, leftblack);

			return false;
			
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data.first > key)
					cur = cur->_left;
				else if (cur->_data.first < key)
					cur = cur->_right;
				else
					return cur;
			}
			return nullptr;
		}

		~RBTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

	private:
		void Destroy(Node* root)
		{
			if (!root) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

		void RotateL(Node* parent) //左单旋
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

			if (subRL) //如果subR的左孩子存在
				subRL->_parent = parent;

			parent->_right = subRL;
			subR->_left = parent;

			Node* grandfather = parent->_parent;
			if (grandfather) //是子树 调整parent的父节点指向
			{
				if (grandfather->_left == parent)
				{
					grandfather->_left = subR;
				}
				else
				{
					grandfather->_right = subR;
				}
				subR->_parent = grandfather;
			}
			else //是根节点
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			parent->_parent = subR;
		}

		void RotateR(Node* parent) //右单旋
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			if (subLR)
				subLR->_parent = parent;

			parent->_left = subLR;
			subL->_right = parent;

			Node* grandfather = parent->_parent;
			if (grandfather)
			{
				if (grandfather->_left == parent)
				{
					grandfather->_left = subL;
				}
				else
				{
					grandfather->_right = subL;
				}
				subL->_parent = grandfather;
			}
			else
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			parent->_parent = subL;
		}

		void _midorder(Node* root) //中序遍历子函数
		{
			if (!root) return;
			_midorder(root->_left);
			cout << root->_data.first << ":" << root->_data.second << endl;
			_midorder(root->_right);
		}

		bool _Check(Node* root, int NodeNum,int BlackNum)
		{
			if (!root)
			{
				//cout << NodeNum << endl; //打印黑色节点数
				if (NodeNum == BlackNum)
					return true;
				else 
					return false;
			}

			if (root->_col == BLACK) //黑色节点就++
				++NodeNum;

			if (root->_col == RED && root->_parent && root->_parent->_col == RED) //不能出现两个连续的红色节点
			{
				cout << "出现两个连续的红色节点：" << root->_parent->_data.first << "和" << root->_data.first << endl;
				return false;
			}

			return _Check(root->_left, NodeNum, BlackNum) && _Check(root->_right, NodeNum, BlackNum);
		}

		Node* copy(Node* root)
		{
			if (!root) return nullptr;

			Node* newnode = new Node(root->_data);
			newnode->_col = root->_col;
			
			newnode->_left = copy(root->_left);
			if (newnode->_left)
				newnode->_left->_parent = newnode;
			newnode->_right = copy(root->_right);
			if (newnode->_right)
				newnode->_right->_parent = newnode;

			return newnode;
		}

	private:
		Node* _root;
		
	};
}